package lc;

import org.junit.Test;

public class Ex209 {
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            //前缀和数组的二分查找
            /* 
                求解前缀和数组的两个下标：i, j (j > i)
                满足sum[j] - sum[i] >= target
    
                可以像TwoSum一样，使用双重循环，先确定sum[i],  只要求解sum[j] >= sum[i] + target,且j越小越好


                巨坑：一旦全部元素都要参与，无法得到左下标。需要在sum最左边放一个0
             */
            int len = nums.length, res = Integer.MAX_VALUE;


            int[] sum = new int[len + 1];
            sum[0] = 0;
            for (int i = 1; i < len + 1; i++) {
                sum[i] = nums[i - 1] + sum[i - 1];
            }
    
            for (int i = 0; i < len + 1; i++) {
                int lo = i, hi = len, mid, t = sum[i] + target;
                while (lo < hi) {
                    mid = (hi - lo) / 2 + lo;
                    if (sum[mid] < t) {
                        lo = mid + 1;
                    } else {
                        //让他尽可能的小
                        hi = mid;
                    }
                }
                if (sum[lo] - sum[i] >= target) {
                    res = Math.min(res, lo - i); //注意i是子数组左外边的位置
                }
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }
    }
    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,3,4,5};

        System.out.println(s.minSubArrayLen(15, nums));
        /* 
        15
[1,2,3,4,5] */
    }
}

